package newcoder_exp.justPractise;
import java.util.*;

import org.junit.Test;

import linked.*;
public class Ex50 {
    class Solution {
        /**
         * 
         * @param head ListNode类 
         * @param k int整型 
         * @return ListNode类
         */
        public ListNode reverseKGroup (ListNode head, int k) {
            if (head == null || head.next == null || k <= 1) return head;
            ListNode cur = head, end, res = new ListNode(0), result = res, start;
            res.next = head;
            while (res != null && res.next!= null) {
                start = res.next;
                end = findEnd(res.next, k);
                if (end != null && end.val == Integer.MIN_VALUE) {
                    return result.next;
                }
                res.next = reverse(res.next, end);
                res = start;
            }
            return result.next;
        }
        
        public ListNode reverse(ListNode head, ListNode end) {
            if (head == end || head.next == end) return head;
            ListNode pre = end, post = head, temp;
            while (post != end) {
                temp = post.next;
                post.next = pre;
                pre = post;
                post = temp;
            }
            head.next = end;
            return pre;
        }
        
        public ListNode findEnd(ListNode cur, int k) {
            while (k > 0 && cur != null) {
                cur = cur.next;
                k--;
            }
            if (k == 0) 
                return cur;
            return new ListNode(Integer.MIN_VALUE);
        }

    }

    @Test
    public void test() {
        int[] nums = {1,2};
        ListNode head = ListNode.newListNodeFromArray(nums);
        Solution s = new Solution();
        head = s.reverseKGroup(head, 2);
        System.out.println(head);
    }
}
